// 1.
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(target > nums[nums.size()-1])
            return nums.size();
        if(target < nums[0])
            return 0;
        int left=0;
        int right = nums.size()-1;        
        int result=0;
        while(left <= right) {
            int mid = ((right - left) >> 1) + left;
            // left + (right - left) / 2 比 (left+right) / 2 减少值溢出
            if(target == nums[mid]) 
                return mid;
               
            else if(target < nums[mid]) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        //二分查找没找见
        for(int i=0;i<nums.size()-1;++i) {
            if(target > nums[i] && target < nums[i+1]) {
                result =  i+1;
                break;
            }
        }

        return result;
    }
};

// 2.
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
       
        int left=0;
        int right = nums.size()-1;        
        
        while(left <= right) {
            int mid = ((right - left) >> 1) + left;
            // left + (right - left) / 2 比 (left+right) / 2 减少值溢出
            if(target == nums[mid]) 
                return mid;
               
            else if(target < nums[mid]) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        return left;
    }
};


/*
关键结论
无论目标值是否存在于数组中，
二分查找结束时，left 指针总是指向：
目标值的第一个出现位置（如果存在）。
第一个大于目标值的元素位置（如果不存在）。

这就是为什么直接返回 left 即可得到正确的插入位置。

*/




